#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cstring>
#include <utility>

using namespace std;

size_t partition(int* arr, size_t begin, size_t end) {
  if (arr) {
    if (begin > end)
      throw "invalid interval when calling partition";

    int pivot = arr[end];
    size_t open = begin;
    size_t cur = begin;

    while (cur < end) {
      if (arr[cur] < pivot)
	swap (arr[open++], arr[cur]);
      cur++;
    }
    swap (arr[open], arr[cur]);
    return open;
  }
}

void quick_sort(int* arr, size_t begin, size_t end) {
  if (arr) {
    if (begin > end)
      throw "invalid interval when calling quick_sort";
   
    if (begin == end) 
      return;

    size_t pivot = partition(arr, begin, end);
    if (begin + 1 < pivot) 
      quick_sort(arr, begin, pivot - 1);
    if (end > pivot + 1)
      quick_sort(arr, pivot + 1, end);
  }
}

// problem 1
void merge(int* A, int n, int* B, int m) {
  int pos = n + m - 1;
  n--; m--;
  while (n >= 0 && m >= 0) {
    if (A[n] > B[m])
      A[pos--] = A[n--];
    else
      A[pos--] = B[m--];
  }
  while (m >= 0) {
    A[pos--] = B[m--];
  }
}

// problem 2
void sort_anagrams(const char* strs[], size_t n) {
  if (strs) {
    sort (strs, strs+n, [] (const char* str1, const char* str2) -> bool {
	size_t len1 = strlen(str1);
	size_t len2 = strlen(str2);

	char* a = new char[len1+1];
	strcpy (a, str1);
	sort (a, a+len1);
	char* b = new char[len2+1];
	strcpy (b, str2);
	sort (b, b+len2);
	
	int cmp = strcmp (a, b);
	delete [] a;
	delete [] b;

	return (cmp <= 0) ? true : false;
      });
  }
}

// problem 3
int find_in_rotation(int* arr, size_t n, int elem) {
  size_t begin = 0;
  size_t end = n-1;

  while (begin <= end) {
    size_t middle = (begin + end) / 2;
    if (arr[middle] == elem)
      return middle;
    
    if (arr[begin] > arr[middle]) {
      if (elem < arr[middle])
	end = middle - 1;
      else if (elem > arr[end])
	end = middle - 1;
      else 
	begin = middle + 1;
    }
    else {
      if (elem > arr[middle])
	begin = middle + 1;
      else if (elem < arr[begin])
	begin = middle + 1;
      else 
	end = middle - 1;
    }
  }
  return -1;
}

// problem 5
int find_str(const char** strs, size_t n, const char* elem) {
  if (strs) {
    int left = 0; 
    int right = n-1;

    while (left <= right) {
      while (right >= left && strs[right] == "")
	right--;
      
      if (left > right)
	return -1;

      size_t middle = (left + right) >> 1;
      while (strs[middle] == "")
	middle++;

      if (strs[middle] == elem) 
	return middle;
      else if (strs[middle] < elem) 
	left = middle + 1;
      else 
	right = middle - 1;
    }
  }
  return -1;
}

// problem 6
template<size_t M, size_t N, typename T>
pair<int, int> find_in_matrix(T matrix[M][N], T elem) {
  int r = 0;
  int c = N-1;
  while (r < M && c >= 0) {
    if (matrix[r][c] == elem)
      return make_pair(r,c);
    else if (matrix[r][c] > elem)
      c--;
    else 
      r++;
  }
  return make_pair(-1,-1);
}

// problem 7



int main() {
  int arr[] = { 5, 1, 3, 6, 9, 0, 1, 5, 7};
  size_t arr_size = sizeof(arr) / sizeof(int);

  cout << "Original array: ";
  copy (arr, arr+arr_size, ostream_iterator<int>(cout, " "));
  cout << endl;
  
  cout << "Test partition" << endl;
  partition(arr, 0, arr_size-1);
  copy (arr, arr+arr_size, ostream_iterator<int>(cout, " "));
  cout << endl;

  cout << "Test quick sort" << endl;
  quick_sort (arr, 0, arr_size-1);
  copy (arr, arr+arr_size, ostream_iterator<int>(cout, " "));
  cout << endl << endl;

  cout << "Test problem 1" << endl;
  int A[] = {0,1,2,3,4,5,6,7,8,9,0,0,0,0,0}; // last 5 are placeholders
  int B[] = {1,3,5,7,9};
  cout << "A array: "; copy (A, A+10, ostream_iterator<int>(cout, " ")); cout << endl;
  cout << "B array: "; copy (B, B+5, ostream_iterator<int>(cout, " ")); cout << endl;
  merge(A, 10, B, 5);
  cout << "After merge: "; copy (A, A+15, ostream_iterator<int>(cout, " ")); cout << endl;
  cout << endl;

  cout << "Test problem 2" << endl;
  const char* anagrams[] = { "a", "bada", "ab", "daab", "ba", "aa" };
  arr_size = sizeof(anagrams) / sizeof(const char*);
  cout << "Original array: "; copy (anagrams, anagrams+arr_size, ostream_iterator<const char*>(cout, " ")); cout << endl;
  sort_anagrams(anagrams, arr_size);
  cout << "After anagrams sorting: "; copy (anagrams, anagrams+arr_size, ostream_iterator<const char*>(cout, " ")); cout << endl;
  cout << endl;

  cout << "Test problem 3" << endl;
  int rotation[] = {15,16,19,20,25,1,3,4,5,7,10,14};
  arr_size = sizeof(rotation) / sizeof(int);
  cout << "Original array: "; copy (rotation, rotation+arr_size, ostream_iterator<int>(cout, " ")); cout << endl;
  int elem = 5;
  cout << "Index of " << elem << " is " << find_in_rotation(rotation, arr_size, elem) << " == 8" << endl;
  elem = 0;
  cout << "Index of " << elem << " is " << find_in_rotation(rotation, arr_size, elem) << " == -1" << endl;
  cout << endl;

  cout << "Test problem 5" << endl;
  const char* strs[] = {"at", "", "", "", "ball", "car", "", "", "dad", "", ""};
  arr_size = sizeof(strs) / sizeof(const char*);
  cout << "Original array: "; copy (strs, strs+arr_size, ostream_iterator<const char*>(cout, " ")); cout << endl;
  cout << "Index of \"ball\" is " << find_str(strs, arr_size, "ball") << " == 4" << endl;
  cout << "Index of \"ballcar\" is " << find_str(strs, arr_size, "ballcar") << " == -1" << endl;
  cout << endl;

  cout << "Test problem 6" << endl;
  const size_t rows = 3;
  const size_t cols = 3;
  int matrix[rows][cols] = {{1,3,6}, {2,5,7}, {4,8,9}};
  pair<int, int> r = find_in_matrix<rows, cols, int>(matrix, 2);
  cout << "Index of 2 is " << "(" << r.first << "," << r.second << ") == (1,0)" << endl;
  r = find_in_matrix<rows, cols, int>(matrix, 0);
  cout << "Index of 0 is " << "(" << r.first << "," << r.second << ") == (-1,-1)" << endl;
  cout << endl;
}
